package com.haidechizi.leetcode;


/**
 * 定义left，right下标
 *
 * 已第一个不为0的值作为left
 *
 * 循环找到第一个>=left的小标作right
 *
 * 如果找不到，执照left之后最大的值作为right，然后将i设置为max+1
 *
 * 通过sum函数计算left到right能够装的雨水
 *
 *
 */
public class _42_接雨水 {

    public int trap(int[] height) {
        if (height == null || height.length <= 2) {
            return 0;
        }

        int sum = 0;
        int left = 0;
        int right = 0;
        for (int i = 0; i < height.length; ) {
            if (height[i] == 0) {
                i++;
                continue;
            }
            if (left == 0 || height[left] == 0) {
                left = i;
                i++;
            }
            // 只剩两个相邻的节点，无法装雨水
            if (i > height.length - 1) {
                break;
            }
            // i++;
            int max = i;
            while ((right == 0 && i < height.length) || (height[right] < height[left] && i < height.length)) {
                // 找到第一个大于left的节点
                if (height[i] >= height[left]) {
                    right = i;
                    break;
                }
                // 找到最大的节点
                if (height[i] >= height[max]) {
                    max = i;
                }
                i++;
            }
            // 找不到哦啊大于left的节点
            if (right == 0) {
                right = max;
                i = max + 1;
            }
            // 计算能够装的雨水
            sum += sum(height, left, right);
            left = right;
            right = 0;
            i++;
        }
        return sum;
    }

    public int sum(int[] height, int left, int right) {
        int min = Math.min(height[left], height[right]);
        int sum = 0;
        for (int i = left + 1; i < right; i++) {
            if (height[i] == min) {
                continue;
            }
            sum += min - height[i];
        }
        return sum;
    }


    public static void main(String[] args) {
        int trap = new _42_接雨水().trap(new int[]{4, 9, 4, 5, 3, 2});

        System.out.println(trap);
    }
}
